package leetcode.offer_two_special.stack;

import java.util.Stack;

/**
 * matrix = ["10100","10111","11111","10010"]
 *
 * @author mazouri
 * @create 2021-09-11 13:16
 */
public class _40_maximalRectangle {
    public int maximalRectangle(String[] matrix) {
        if (matrix == null || matrix.length == 0) return 0;

        int[] heights = new int[matrix[0].length()];
        int maxArea = 0;
        for (String s : matrix) {
            for (int i = 0; i < s.length(); i++) {
                heights[i] = s.charAt(i) == '0' ? 0 : heights[i] + 1;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }


    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                int curArea = (i - k - 1) * heights[j];
                maxArea = Math.max(maxArea, curArea);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (heights.length - k - 1) * heights[j];
            maxArea = Math.max(maxArea, curArea);
        }

        return maxArea;
    }
}
